package algorithm.排序;

import java.util.Arrays;
import java.util.List;

class InsertionSort {

    static void print(List<?> toPrint) {
        toPrint.stream().map(Object::toString).map(str -> str + "  ").forEach(System.out::print);
        System.out.println();
    }

    public Integer[] sort(Integer[] array) {
        for (int i = 1; i < array.length; i++) {
            int insertValue = array[i];
            int j;
            for (j = i - 1; j >= 0 && insertValue < array[j]; j--) {
                array[j + 1] = array[j];
            }
            if (j != i - 1) {
                array[j + 1] = insertValue;
            }
        }
        return array;
    }

    public static void main(String[] args) {
        Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};
        InsertionSort sort = new InsertionSort();
        sort.sort(integers);
        print(Arrays.asList(integers));
    }
}

// 由下面代码改造而来
// https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/InsertionSort.java

